TCAMs (ternary content addressable memory) are known in the art. They are units which store data of three states, 0, 1 or X (don't care) and are generally used to store data which needs to be searched, such as addresses of nodes in a network or phone numbers. TCAMs are used for parallel searching of an input “key” or part of a key within large databases. For example, if the key is 101 and the stored data are 1XX, 101, XXX, 010, 001, 100, the first three values will be matched while the next three values will not be matched.
Because the data has three possible states, a range of values may be represented by one key using the X state. Thus, 1XX represents the keys 111, 110, 101 and 100.
An exemplary TCAM unit is shown in FIG. 1, to which reference is now made. The data is stored in plurality of columns 10, where each column stores one key and each key is associated with a pointer to a further memory which stores other information related to the key. Thus, if the key is a network address, such as is the case for an access control list (ACL) search, the pointer may point to the output port for that network address. The pointer may also point to information about how to process the address, such as to ignore it or to pass it on.
Each individual TCAM unit has its own comparison circuit to detect a match between the stored bit (1, 0, or X (Don't Care)) and the input bit (1 or 0). The individual TCAM units are connected together in rows by word lines and in columns by bit lines. When an input key 12 (i.e. a port number or IP source or destination address) is received for searching in the TCAM, the values of the elements of the key are separately provided to the rows, to be simultaneously matched by each TCAM unit of the row. Thus, the first bit of the key is provided to the first row, the second bit to the second row, etc. The output of the TCAM is read by the columns. A match occurs when all of the TCAM units in a column are matched to the bits of the input key.
Each column is associated with a pointer 14, pointing to a section of a DRAM (dynamic random access memory) 16 in which information about the key is stored. For example, if the key refers to an address within a network, the information in DRAM 16 may be out of which port of the switch, where the TCAM may be located, to transmit the packet having the input address.
The problem with TCAM units is that each TCAM unit requires both a memory element and a comparison circuit. Thus, TCAM units are relatively large (compared to simple memory units which don't have the comparison circuits) and thus are not built to store very large amounts of data to be matched.